// https://www.lintcode.com/problem/maximum-product-subarray/my-submissions

class Solution {
public:
    /**
     * @param nums: An array of integers
     * @return: An integer
     */
    int maxProduct(vector<int> &nums) {
        /////////////错误解法//////////////////
//         错的，这样中间可能断了
// Input
// [-3,1,-2]
// Output
// 1
// Expected
// 6
//         vector<int> mat = nums;
//         for (int i = 1; i < nums.size(); ++i)
//         {
//             mat[i] = max(mat[i], mat[i - 1] * nums[i]);
//         }
//         // 错的，要连续的，有起始
//         // return mat.back();
//         int result = INT_MIN;
//         for (int i = 0; i < nums.size(); ++i)
//         {
//             result = max(result, mat[i]);
//         }
//         return result;
        
//         MLE
//         int n = nums.size();
//         vector<vector<int>> mat(n, vector<int>(n, INT_MIN));
//         int result = INT_MIN;
//         for (int i = 0; i < nums.size(); ++i)
//         {
//             for (int j = i; j < nums.size(); ++j)
//             {
//                 if (j == i) mat[i][j] = nums[i];
//                 else mat[i][j] = mat[i][j - 1] * nums[j];
//                 if (mat[i][j] > result) result = mat[i][j];
//             }
//         }
//         return result;
       
//         和加法思路不一样。加法只要变成负的，就不如从新的开始加。 
//         int pro = 1;
//         int result = INT_MIN;
//         for (int i = 0; i < nums.size(); ++i)
//         {
//             pro *= nums[i];
//             result = max(result, pro);
//             pro = max(pro, 1);
//         }
//         return result;
        
//         vector<int> mat(nums.size() + 1);
//         mat[0] = 1;
//         for (int i = 1; i < nums.size() + 1; ++i)
//         {
//             mat[i] = mat[i - 1] * nums[i - 1];
//         }
//         int result = INT_MIN;
//         for (int i = 0; i < nums.size() + 1; ++i)
//         {
//             for (int j = i + 1; j < nums.size() + 1; ++j)
//                 result = max(result, mat[j] / mat[i]); // 有0，[-3,0,1,-2]
//         }
//         return result;
                /////////////错误解法//////////////////

// 动态规划，因为有正负的情况，维护两个数组，最大值和最小值
// 确定状态:
// 最后一步: 考虑最后一个数A[n], 那么乘积最大的就是前面以n - 1为结尾的最大乘积, 再乘上这个数
// 子问题: 如果要求以n为结尾的子数组的最大乘积, 先要求以n - 1为结尾的最大乘积
// 在这里要注意, 如果A[n]是个负数, 因为负负得正, 所以我们需要以n - 1为结尾的最小乘积

// 转移方程:
// 维护两个数组, f[i] 和 g[i], f[i]用于记录最大值, g[i]用于记录最小值.
// A[i]代表数组中的第i个数
// 转移方程: f[i] = max(f[i - 1] * A[i], g[i - 1] * A[i], A[i])
// g[i] = min(f[i - 1] * A[i], g[i - 1] * A[i], A[i])
// 初始条件与边界情况:
// f[0] = A[0], g[0] = A[0]
// 计算顺序:
// 从左往右
// 最终结果max(i -> 0...n | f[i])
        vector<int> maxRec(nums.size(), INT_MIN);
        vector<int> minRec(nums.size(), INT_MAX);
        maxRec[0] = nums[0];
        minRec[0] = nums[0];
        // int result = INT_MIN;
        int result = nums[0];
        for (int i = 1; i < nums.size(); ++i)
        {
            // if (nums[i] > 0)
            // {
            //     maxRec[i] = max(maxRec[i - 1] * nums[i], nums[i]);
            //     minRec[i] = min(minRec[i - 1] * nums[i], nums[i]);
            // }
            // else
            // {
            //     maxRec[i] = max(minRec[i - 1] * nums[i], nums[i]);
            //     minRec[i] = min(maxRec[i - 1] * nums[i], nums[i]);
            // }
            maxRec[i] = max(max(maxRec[i - 1] * nums[i], minRec[i - 1] * nums[i]), nums[i]);
            minRec[i] = min(min(maxRec[i - 1] * nums[i], minRec[i - 1] * nums[i]), nums[i]);
            
            result = max(result, maxRec[i]);
        }
        return result;
        
        // 法二：贪心。如果是负数导致的变小，那么从第一个负数后面开始乘
        // int pro = 1;
        // int result = INT_MIN;
        // int negPro = 0; //记录0后面第一个负数出现的位置,从这个后面乘就少一个负数
        // for (int i = 0; i < nums.size(); ++i)
        // {
        //     if(negPro != 0) 
        //     {
        //         negPro *= nums[i];
        //         result = max(negPro, result);
        //     }
        //     pro *= nums[i];
        //     if (nums[i] < 0 && negPro == 0) 
        //     {
        //         negPro = 1;
        //     }
        //     result = max(result, pro);
        //     if (pro == 0)
        //     {
        //         pro = 1;
        //         negPro = 0;
        //     }
        // }
        // return result;
    }
};